﻿namespace FiniteAutomaton
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    public class Parser
    {
        private Stack<Operator> operatorStack = new Stack<Operator>();
        private Stack<NondeterministicFiniteAutomaton> nfaStack = new Stack<NondeterministicFiniteAutomaton>();

        private Dictionary<State, int> layerAssignment = new Dictionary<State, int>();
        private Dictionary<State, int> positionAssignment = new Dictionary<State, int>();
        private Dictionary<NondeterministicFiniteAutomaton, int> width = new Dictionary<NondeterministicFiniteAutomaton, int>();

        // The order of the members is used for determining precedence. Do not change.
        private enum Operator
        {
            Invalid, Star, Concat, Union, LeftParen, RightParen
        }

        public NondeterministicFiniteAutomaton CreateNFA(string s)
        {
            // Thompson's construction. Reference: algorithm 3.3, Aho, Sethi, and Ullman
            // Instead of converting the input into a postfix representation, like most expression
            // evaluator do, we keep a stack of operands and a stack of operators
            while (nfaStack.Count() != 0)
            {
                nfaStack.Pop();
            }

            while (operatorStack.Count() != 0)
            {
                operatorStack.Pop();
            }

            for (int i = 0; i < s.Length; i++)
            {
                char c = s[i];

                if (!IsOperator(c))
                {
                    SingleChar(c);
                }
                else
                {
                    Operator op = ToOperator(c);
                    if (op == Operator.LeftParen)
                    {
                        operatorStack.Push(op);
                    }
                    else if (op == Operator.RightParen)
                    {
                        // Evaluate everyting in paranthesis. They have the highest precedence.
                        while (operatorStack.Count() > 0 && operatorStack.Peek() != Operator.LeftParen)
                        {
                            Reduce();
                        }

                        if (operatorStack.Count() == 0)
                        {
                            throw new Exception("Unmatched ')'");
                        }

                        // Pop the matching left paranthesis
                        operatorStack.Pop();
                    }
                    else
                    {
                        while (operatorStack.Count() > 0 && operatorStack.Peek() <= op)
                        {
                            Reduce();
                        }

                        operatorStack.Push(op);
                    }
                }

                // Push a Concat on the operator stack if there is a contact operation coming up.
                // This is needed because concat operation is implicit, unlike other operators.
                // Before doing that, evaluate the stack till we see a lower precedence operator.
                if (i != s.Length - 1)
                {
                    char next = s[i + 1];
                    if ((!IsOperator(c) || c == ')' || c == '*') && (!IsOperator(next) || next == '('))
                    {
                        while (operatorStack.Count() > 0 && operatorStack.Peek() <= Operator.Concat)
                        {
                            Reduce();
                        }

                        operatorStack.Push(Operator.Concat);
                    }
                }
            }

            while (operatorStack.Count() > 0)
            {
                Reduce();
            }

            return nfaStack.Pop();
        }

        private void Reduce()
        {
            Operator op = operatorStack.Pop();

            switch (op)
            {
                case Operator.Star:
                    Star();
                    break;
                case Operator.Union:
                    Union();
                    break;
                case Operator.Concat:
                    Concat();
                    break;
            }
        }

        private void Concat()
        {
            NondeterministicFiniteAutomaton nfa2 = nfaStack.Pop();
            NondeterministicFiniteAutomaton nfa1 = nfaStack.Peek();

            // Now merge nfa1's final state with nfa2's starting state.
            State s1 = nfa1.States.PeekBack();
            State s2 = nfa2.States.PopFront();
            foreach (LabeledEdge<State, char> t in nfa2.Transitions)
            {
                if (t.Source == s2)
                {
                    nfa1.Transitions.Add(new LabeledEdge<State, char>(s1, t.Target, t.Label));
                }
                else
                {
                    nfa1.Transitions.Add(t);
                }
            }

            // Add table2's states to table1.
            foreach (State s in nfa2.States)
            {
                nfa1.States.AddBack(s);

                // Layer adjustment for states in nfa2
                layerAssignment[s] += layerAssignment[s1];
            }

            // Position adjustment for the nfa which is narrower
            int width1 = width[nfa1];
            int width2 = width[nfa2];

            if (width1 > width2)
            {
                int delta = (width1 - width2) / 2;
                foreach (State s in nfa2.States)
                {
                    positionAssignment[s] += delta;
                }
            }
            else if (width2 > width1)
            {
                width[nfa1] = width2;

                int delta = (width2 - width1) / 2;
                foreach (State s in nfa1.States)
                {
                    positionAssignment[s] += delta;
                }
            }
        }

        private void Star()
        {
            if (nfaStack.Count() == 0)
            {
                throw new Exception("Unexpected *, missing operand");
            }

            NondeterministicFiniteAutomaton nfa = nfaStack.Peek();

            State start = new State();
            State end = new State();

            nfa.Transitions.Add(new LabeledEdge<State, char>(start, end, (char)0));
            nfa.Transitions.Add(new LabeledEdge<State, char>(start, nfa.States.PeekFront(), (char)0));
            nfa.Transitions.Add(new LabeledEdge<State, char>(nfa.States.PeekBack(), end, (char)0));
            nfa.Transitions.Add(new LabeledEdge<State, char>(nfa.States.PeekBack(), nfa.States.PeekFront(), (char)0));

            nfa.States.AddBack(end);
            nfa.States.AddFront(start);

            // Layout adjustment
            int w = width[nfa] + 2;
            width[nfa] = w;

            positionAssignment[start] = (w - 1) / 2;
            positionAssignment[end] = (w - 1) / 2;
            layerAssignment[start] = 0;
            layerAssignment[end] = layerAssignment[nfa.States.PeekBack()] + 2;

            foreach (State s in nfa.States)
            {
                layerAssignment[s]++;
                positionAssignment[s]++;
            }
        }

        private void Union()
        {
            if (nfaStack.Count() == 0)
            {
                throw new Exception("Unexpected |, missing both operands");
            }

            NondeterministicFiniteAutomaton nfa2 = nfaStack.Pop();

            if (nfaStack.Count() == 0)
            {
                throw new Exception("Unexpected |, missing left operand");
            }

            NondeterministicFiniteAutomaton nfa1 = nfaStack.Peek();

            State s1 = nfa1.States.PeekFront();
            State s2 = nfa2.States.PeekFront();

            State f1 = nfa1.States.PeekBack();
            State f2 = nfa2.States.PeekBack();

            State start = new State();
            State end = new State();

            nfa1.States.AddFront(start);
            nfa1.States.AddRangeBack(nfa2.States);
            nfa1.States.AddBack(end);

            nfa1.Transitions.AddRange(nfa2.Transitions);
            nfa1.Transitions.Add(new LabeledEdge<State, char>(start, s1, (char)0));
            nfa1.Transitions.Add(new LabeledEdge<State, char>(start, s2, (char)0));
            nfa1.Transitions.Add(new LabeledEdge<State, char>(f1, end, (char)0));
            nfa1.Transitions.Add(new LabeledEdge<State, char>(f2, end, (char)0));

            // Layout adjustment
            int width1 = width[nfa1];
            int width2 = width[nfa2];
            int height1 = layerAssignment[f1];
            int height2 = layerAssignment[f2];

            int w = Math.Max(width1, width2);
            int h = Math.Max(height1, height2);

            // New width
            width[nfa1] = w * 2 + 1;

            // Layer and position of start and final states
            layerAssignment[start] = 0;
            positionAssignment[start] = w;

            layerAssignment[end] = Math.Max(height1, height2) + 2;
            positionAssignment[end] = w * 2 + 1;

            // Reposition other states
            int delta1 = (3 * w + 1) / 2 - positionAssignment[s1];
            int delta2 = (w-1)/2 - positionAssignment[s2];

            double stretch1 = (double)h / (double)height1;
            double stretch2 = (double)h / (double)height2;

            foreach (State s in nfa1.States)
            {
                positionAssignment[s] += delta1;
                layerAssignment[s] *= (int) (layerAssignment[s] * stretch1) + 1;
            }

            foreach (State s in nfa2.States)
            {
                positionAssignment[s] += delta2;
                layerAssignment[s] *= (int)(layerAssignment[s] * stretch2) + 1;
            }
        }

        private void SingleChar(char ch)
        {
            State state1 = new State();
            State state2 = new State();

            NondeterministicFiniteAutomaton nfa = new NondeterministicFiniteAutomaton();
            nfa.States.AddBack(state1);
            nfa.States.AddBack(state2);

            nfa.Transitions.Add(new LabeledEdge<State, char>(state1, state2, ch));
            nfaStack.Push(nfa);

            // Layout information
            layerAssignment[state1] = 0;
            layerAssignment[state2] = 1;
            positionAssignment[state1] = 0;
            positionAssignment[state2] = 0;
            width[nfa] = 1;
        }

        private Operator ToOperator(char ch)
        {
            switch (ch)
            {
                case '*':
                    return Operator.Star;
                case '|':
                    return Operator.Union;
                case '(':
                    return Operator.LeftParen;
                case ')':
                    return Operator.RightParen;
            }

            return Operator.Invalid;
        }

        private bool IsOperator(char ch)
        {
            return ToOperator(ch) != Operator.Invalid;
        }
    }
}
